SPOJ/MATSUM - 1029. Matrix Summation/matsum.cpp

   1 using namespace std;
   2 #include <algorithm>
   3 #include <iostream>
   4 #include <iterator>
   5 #include <numeric>
   6 #include <sstream>
   7 #include <fstream>
   8 #include <cassert>
   9 #include <climits>
  10 #include <cstdlib>
  11 #include <cstring>
  12 #include <string>
  13 #include <cstdio>
  14 #include <vector>
  15 #include <cmath>
  16 #include <queue>
  17 #include <deque>
  18 #include <stack>
  19 #include <list>
  20 #include <map>
  21 #include <set>
  22
  23 #define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
  24 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  25 #define D(x) cout << #x " is " << x << endl
  26
  27 const int MAXN = 1025;
  28 int tree[MAXN][MAXN];
  29 int mat[MAXN][MAXN];
  30 int N;
  31
  32 void add(int r, int c, int what) {
  33     for (r++; r <= N; r += r & -r) {
  34         for (int d = c + 1; d <= N; d += d & -d) {
  35             tree[r][d] += what;
  36         }
  37     }
  38 }
  39
  40 int get(int r, int c) {
  41     int ans = 0;
  42     for (r++; r > 0; r -= r & -r) {
  43         for (int d = c + 1; d > 0; d -= d & -d) {
  44             ans += tree[r][d];
  45         }
  46     }
  47     return ans;
  48 }
  49
  50 int sum(int r1, int c1, int r2, int c2) {
  51     return get(r2, c2) - get(r1 - 1, c2) - get(r2, c1 - 1) + get(r1 - 1, c1 - 1);
  52 }
  53
  54 void set(int r, int c, int what) {
  55     int prev = mat[r+1][c+1];
  56     mat[r+1][c+1] = what;
  57     add(r, c, what - prev);
  58 }
  59
  60 int main(){
  61     int t; scanf("%d", &t);
  62     while (t--) {
  63         scanf("%d", &N);
  64         for (int i = 0; i <= N; ++i) {
  65             for (int j = 0; j <= N; ++j) {
  66                 tree[i][j] = mat[i][j] = 0;
  67             }
  68         }
  69         while (true) {
  70             char buf[4];
  71             scanf("%s", buf);
  72             if (!strcmp(buf, "SET")) {
  73                 int r, c, x; scanf("%d %d %d", &r, &c, &x);
  74                 //printf("Set (%d, %d) to %d\n", r, c, x);
  75                 ::set(r, c, x);
  76             } else if (!strcmp(buf, "SUM")) {
  77                 int r1, c1, r2, c2; scanf("%d %d %d %d", &r1, &c1, &r2, &c2);
  78                 //printf("Sum (%d, %d) to (%d, %d)\n", r1, c1, r2, c2);
  79                 int ans = sum(r1, c1, r2, c2);
  80                 printf("%d\n", ans);
  81             } else {
  82                 //printf("Take a break.\n");
  83                 break;
  84             }
  85         }
  86         printf("\n");
  87     }
  88     return 0;
  89 }